// A C / C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Number of vertices in the graph
int V;

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], int sptSet[]){
	int v;

	// Initialize min value
	int min = INT_MAX, min_index;

	for (v = 0; v < V; v++)
		if (sptSet[v] == 0 && dist[v] <= min)
			min = dist[v], min_index = v;

	return min_index;
}


// Funtion that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
int* dijkstra(int **graph, int src){
	int i, count, v;
    int *dist;	// The output array.  dist[i] will hold the shortest
	            // distance from src to i

	int sptSet[V]; // sptSet[i] will true (1) if vertex i is included in shortest
					// path tree or shortest distance from src to i is finalized

	dist = (int*)malloc(V*sizeof(int));

	// Initialize all distances as INFINITE and stpSet[] as false (0)
	for (i = 0; i < V; i++)
		dist[i] = INT_MAX, sptSet[i] = 0;

	// Distance of source vertex from itself is always 0
	dist[src] = 0;
 
	// Find shortest path for all vertices
	for (count = 0; count < V-1; count++){
		// Pick the minimum distance vertex from the set of vertices not
		// yet processed. u is always equal to src in first iteration.
		int u = minDistance(dist, sptSet);
 
		// Mark the picked vertex as processed
		sptSet[u] = 1;
		
		// Update dist value of the adjacent vertices of the picked vertex.
		for (v = 0; v < V; v++)
			// Update dist[v] only if is not in sptSet, there is an edge from
			// u to v, and total weight of path from src to  v through u is
			// smaller than current value of dist[v]
			if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u]+graph[u][v] < dist[v])
				dist[v] = dist[u] + graph[u][v];
	}

	return dist;
}

void printPath(int **g){
	int i, j;
	for(i=0; i<V; i++){
		printf("%d ->", i);
		for(j=0; j<V; j++){
			printf("\t%d", g[i][j]);
		}
		printf("\n");
	}
}

int main(){
	int m, i, j, u, v;
	int min_of_max;	// The min path value of all max path value
	int central_vertex;
	int **graph;	// Graph matrix
	int **min_paths;	// Min paths for all Vertex
	int *max_path;	// Max path value for each Vertex   

	scanf("%d %d", &V, &m);

	// Allocating graphs, paths,
	graph = (int**)calloc(V, sizeof(int*));
	min_paths = (int**)calloc(V, sizeof(int*));
	max_path = (int*)calloc(V, sizeof(int));

    if (graph == NULL || min_paths == NULL || max_path == NULL)
		return -1;

	for(i=0; i<V; i++){
		graph[i] = (int*)calloc(V, sizeof(int));
	}


	// Initializing Graph
	for(i=0; i<m; i++){
		scanf("%d %d", &u, &v);
		scanf("%d", &graph[u-1][v-1]);
		graph[v-1][u-1] = graph[u-1][v-1];
	}

	// Calculating minimal path for all vertex
	for(i=0; i<V; i++){
		min_paths[i] = dijkstra(graph, i);
	}
	
	// Search max distance path for each vertex
	min_of_max = INT_MAX;
	central_vertex = -1;
	for(i=0; i<V; i++){
		max_path[i] = -1;	//initialize max path with lower value 
		for(j=0; j<V; j++){
			if(min_paths[i][j] > max_path[i])
				max_path[i] = min_paths[i][j];
		}
		if(min_of_max > max_path[i]){
			min_of_max = max_path[i];
			central_vertex = i;
		}
	}

	// Freeing memory
	for(i=0; i<V; i++){
		free(graph[i]);
		free(min_paths[i]);
	}

	free(graph);
	free(min_paths);
	free(max_path);

	//printPath(min_paths);
	//printf("\nVertex(%d) > distance %d\n\n\n", central_vertex, min_of_max);

	return 0;
}

